home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 1995 August: Tool Chest / Dev.CD Aug 95 TC / Dev.CD Aug 95 TC.toast / Tool Chest / Development Tools & Languages / Dylan Related / Marlais / Marlais 0.5.9-portable sources / gc / mark.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-03-15  |  29.1 KB  |  1,062 lines  |  [TEXT/ttxt]
  1.  
  2. /*
  3.  * Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers
  4.  * Copyright (c) 1991-1995 by Xerox Corporation.  All rights reserved.
  5.  *
  6.  * THIS MATERIAL IS PROVIDED AS IS, WITH ABSOLUTELY NO WARRANTY EXPRESSED
  7.  * OR IMPLIED.  ANY USE IS AT YOUR OWN RISK.
  8.  *
  9.  * Permission is hereby granted to use or copy this program
  10.  * for any purpose,  provided the above notices are retained on all copies.
  11.  * Permission to modify the code and to distribute modified code is granted,
  12.  * provided the above notices are retained, and a notice that the code was
  13.  * modified is included with the above copyright notice.
  14.  *
  15.  */
  16.  
  17.  
  18. # include <stdio.h>
  19. # include "gc_priv.h"
  20. # include "gc_mark.h"
  21.  
  22. /* We put this here to minimize the risk of inlining. */
  23. /*VARARGS*/
  24. void GC_noop() {}
  25.  
  26. mark_proc GC_mark_procs[MAX_MARK_PROCS] = {0};
  27. word GC_n_mark_procs = 0;
  28.  
  29. /* Initialize GC_obj_kinds properly and standard free lists properly.      */
  30. /* This must be done statically since they may be accessed before     */
  31. /* GC_init is called.                            */
  32. /* It's done here, since we need to deal with mark descriptors.        */
  33. struct obj_kind GC_obj_kinds[MAXOBJKINDS] = {
  34. /* PTRFREE */ { &GC_aobjfreelist[0], 0 /* filled in dynamically */,
  35.         0 | DS_LENGTH, FALSE, FALSE },
  36. /* NORMAL  */ { &GC_objfreelist[0], 0,
  37. #        ifdef ADD_BYTE_AT_END
  38.         (word)(WORDS_TO_BYTES(-1)) | DS_LENGTH,
  39. #        else
  40.         0 | DS_LENGTH,
  41. #        endif
  42.         TRUE /* add length to descr */, TRUE },
  43. /* UNCOLLECTABLE */
  44.           { &GC_uobjfreelist[0], 0,
  45.         0 | DS_LENGTH, TRUE /* add length to descr */, TRUE },
  46. # ifdef STUBBORN_ALLOC
  47. /*STUBBORN*/ { &GC_sobjfreelist[0], 0,
  48.         0 | DS_LENGTH, TRUE /* add length to descr */, TRUE },
  49. # endif
  50. };
  51.  
  52. # ifdef STUBBORN_ALLOC
  53.   int GC_n_kinds = 4;
  54. # else
  55.   int GC_n_kinds = 3;
  56. # endif
  57.  
  58.  
  59. # define INITIAL_MARK_STACK_SIZE (1*HBLKSIZE)
  60.         /* INITIAL_MARK_STACK_SIZE * sizeof(mse) should be a     */
  61.         /* multiple of HBLKSIZE.                */
  62.  
  63. /*
  64.  * Limits of stack for GC_mark routine.
  65.  * All ranges between GC_mark_stack(incl.) and GC_mark_stack_top(incl.) still
  66.  * need to be marked from.
  67.  */
  68.  
  69. word GC_n_rescuing_pages;    /* Number of dirty pages we marked from */
  70.                 /* excludes ptrfree pages, etc.        */
  71.  
  72. mse * GC_mark_stack;
  73.  
  74. word GC_mark_stack_size = 0;
  75.  
  76. mse * GC_mark_stack_top;
  77.  
  78. static struct hblk * scan_ptr;
  79.  
  80. mark_state_t GC_mark_state = MS_NONE;
  81.  
  82. bool GC_mark_stack_too_small = FALSE;
  83.  
  84. bool GC_objects_are_marked = FALSE;    /* Are there collectable marked    */
  85.                     /* objects in the heap?        */
  86.  
  87. bool GC_collection_in_progress()
  88. {
  89.     return(GC_mark_state != MS_NONE);
  90. }
  91.  
  92. /* clear all mark bits in the header */
  93. void GC_clear_hdr_marks(hhdr)
  94. register hdr * hhdr;
  95. {
  96.     BZERO(hhdr -> hb_marks, MARK_BITS_SZ*sizeof(word));
  97. }
  98.  
  99. /*
  100.  * Clear all mark bits associated with block h.
  101.  */
  102. /*ARGSUSED*/
  103. static void clear_marks_for_block(h, dummy)
  104. struct hblk *h;
  105. word dummy;
  106. {
  107.     register hdr * hhdr = HDR(h);
  108.     
  109.     if (hhdr -> hb_obj_kind == UNCOLLECTABLE) return;
  110.         /* Mark bit for these is cleared only once the object is     */
  111.         /* explicitly deallocated.  This either frees the block, or    */
  112.         /* the bit is cleared once the object is on the free list.    */
  113.     GC_clear_hdr_marks(hhdr);
  114. }
  115.  
  116. /* Slow but general routines for setting/clearing/asking about mark bits */
  117. void GC_set_mark_bit(p)
  118. ptr_t p;
  119. {
  120.     register struct hblk *h = HBLKPTR(p);
  121.     register hdr * hhdr = HDR(h);
  122.     register int word_no = (word *)p - (word *)h;
  123.     
  124.     set_mark_bit_from_hdr(hhdr, word_no);
  125. }
  126.  
  127. void GC_clear_mark_bit(p)
  128. ptr_t p;
  129. {
  130.     register struct hblk *h = HBLKPTR(p);
  131.     register hdr * hhdr = HDR(h);
  132.     register int word_no = (word *)p - (word *)h;
  133.     
  134.     clear_mark_bit_from_hdr(hhdr, word_no);
  135. }
  136.  
  137. bool GC_is_marked(p)
  138. ptr_t p;
  139. {
  140.     register struct hblk *h = HBLKPTR(p);
  141.     register hdr * hhdr = HDR(h);
  142.     register int word_no = (word *)p - (word *)h;
  143.     
  144.     return(mark_bit_from_hdr(hhdr, word_no));
  145. }
  146.  
  147.  
  148. /*
  149.  * Clear mark bits in all allocated heap blocks.  This invalidates
  150.  * the marker invariant, and sets GC_mark_state to reflect this.
  151.  * (This implicitly starts marking to reestablish the
  152.  */
  153. void GC_clear_marks()
  154. {
  155.     GC_apply_to_all_blocks(clear_marks_for_block, (word)0);
  156.     GC_objects_are_marked = FALSE;
  157.     GC_mark_state = MS_INVALID;
  158.     scan_ptr = 0;
  159. #   ifdef GATHERSTATS
  160.     /* Counters reflect currently marked objects: reset here */
  161.         GC_composite_in_use = 0;
  162.         GC_atomic_in_use = 0;
  163. #   endif
  164.  
  165. }
  166.  
  167. /* Initiate full marking.    */
  168. void GC_initiate_full()
  169. {
  170. #   ifdef PRINTSTATS
  171.     GC_printf2("***>Full mark for collection %lu after %ld allocd bytes\n",
  172.           (unsigned long) GC_gc_no+1,
  173.              (long)WORDS_TO_BYTES(GC_words_allocd));
  174. #   endif
  175.     GC_promote_black_lists();
  176.     GC_reclaim_or_delete_all();
  177.     GC_clear_marks();
  178.     GC_read_dirty();
  179. #   ifdef STUBBORN_ALLOC
  180.         GC_read_changed();
  181. #   endif
  182. #   ifdef CHECKSUMS
  183.     {
  184.         extern void GC_check_dirty();
  185.         
  186.         GC_check_dirty();
  187.     }
  188. #   endif
  189. #   ifdef GATHERSTATS
  190.     GC_n_rescuing_pages = 0;
  191. #   endif
  192. }
  193.  
  194. /* Initiate partial marking.    */
  195. /*ARGSUSED*/
  196. void GC_initiate_partial()
  197. {
  198.     if (GC_dirty_maintained) GC_read_dirty();
  199. #   ifdef STUBBORN_ALLOC
  200.         GC_read_changed();
  201. #   endif
  202. #   ifdef CHECKSUMS
  203.     {
  204.         extern void GC_check_dirty();
  205.         
  206.         if (GC_dirty_maintained) GC_check_dirty();
  207.     }
  208. #   endif
  209. #   ifdef GATHERSTATS
  210.     GC_n_rescuing_pages = 0;
  211. #   endif
  212.     if (GC_mark_state == MS_NONE) {
  213.         GC_mark_state = MS_PUSH_RESCUERS;
  214.     } else if (GC_mark_state != MS_INVALID) {
  215.         ABORT("unexpected state");
  216.     } /* else this is really a full collection, and mark    */
  217.       /* bits are invalid.                    */
  218.     scan_ptr = 0;
  219. }
  220.  
  221.  
  222. static void alloc_mark_stack();
  223.  
  224. /* Perform a small amount of marking.            */
  225. /* We try to touch roughly a page of memory.        */
  226. /* Return TRUE if we just finished a mark phase.    */
  227. bool GC_mark_some()
  228. {
  229.     switch(GC_mark_state) {
  230.         case MS_NONE:
  231.             return(FALSE);
  232.             
  233.         case MS_PUSH_RESCUERS:
  234.             if (GC_mark_stack_top
  235.                 >= GC_mark_stack + INITIAL_MARK_STACK_SIZE/4) {
  236.                 GC_mark_from_mark_stack();
  237.                 return(FALSE);
  238.             } else {
  239.                 scan_ptr = GC_push_next_marked_dirty(scan_ptr);
  240.                 if (scan_ptr == 0) {
  241. #            ifdef PRINTSTATS
  242.             GC_printf1("Marked from %lu dirty pages\n",
  243.                    (unsigned long)GC_n_rescuing_pages);
  244. #            endif
  245.                     GC_push_roots(FALSE);
  246.                     GC_objects_are_marked = TRUE;
  247.                     if (GC_mark_state != MS_INVALID) {
  248.                         GC_mark_state = MS_ROOTS_PUSHED;
  249.                     }
  250.                 }
  251.             }
  252.             return(FALSE);
  253.         
  254.         case MS_PUSH_UNCOLLECTABLE:
  255.             if (GC_mark_stack_top
  256.                 >= GC_mark_stack + INITIAL_MARK_STACK_SIZE/4) {
  257.                 GC_mark_from_mark_stack();
  258.                 return(FALSE);
  259.             } else {
  260.                 scan_ptr = GC_push_next_marked_uncollectable(scan_ptr);
  261.                 if (scan_ptr == 0) {
  262.                     GC_push_roots(TRUE);
  263.                     GC_objects_are_marked = TRUE;
  264.                     if (GC_mark_state != MS_INVALID) {
  265.                         GC_mark_state = MS_ROOTS_PUSHED;
  266.                     }
  267.                 }
  268.             }
  269.             return(FALSE);
  270.         
  271.         case MS_ROOTS_PUSHED:
  272.             if (GC_mark_stack_top >= GC_mark_stack) {
  273.                 GC_mark_from_mark_stack();
  274.                 return(FALSE);
  275.             } else {
  276.                 GC_mark_state = MS_NONE;
  277.                 if (GC_mark_stack_too_small) {
  278.                     alloc_mark_stack(2*GC_mark_stack_size);
  279.                 }
  280.                 return(TRUE);
  281.             }
  282.             
  283.         case MS_INVALID:
  284.         case MS_PARTIALLY_INVALID:
  285.         if (!GC_objects_are_marked) {
  286.         GC_mark_state = MS_PUSH_UNCOLLECTABLE;
  287.         return(FALSE);
  288.         }
  289.             if (GC_mark_stack_top >= GC_mark_stack) {
  290.                 GC_mark_from_mark_stack();
  291.                 return(FALSE);
  292.             }
  293.             if (scan_ptr == 0
  294.                 && (GC_mark_state == MS_INVALID || GC_mark_stack_too_small)) {
  295.                 alloc_mark_stack(2*GC_mark_stack_size);
  296.         GC_mark_state = MS_PARTIALLY_INVALID;
  297.             }
  298.             scan_ptr = GC_push_next_marked(scan_ptr);
  299.             if (scan_ptr == 0 && GC_mark_state == MS_PARTIALLY_INVALID) {
  300.                 GC_push_roots(TRUE);
  301.                 GC_objects_are_marked = TRUE;
  302.                 if (GC_mark_state != MS_INVALID) {
  303.                     GC_mark_state = MS_ROOTS_PUSHED;
  304.                 }
  305.             }
  306.             return(FALSE);
  307.         default:
  308.             ABORT("GC_mark_some: bad state");
  309.             return(FALSE);
  310.     }
  311. }
  312.  
  313.  
  314. bool GC_mark_stack_empty()
  315. {
  316.     return(GC_mark_stack_top < GC_mark_stack);
  317. }    
  318.  
  319. #ifdef PROF_MARKER
  320.     word GC_prof_array[10];
  321. #   define PROF(n) GC_prof_array[n]++
  322. #else
  323. #   define PROF(n)
  324. #endif
  325.  
  326. /* Given a pointer to someplace other than a small object page or the    */
  327. /* first page of a large object, return a pointer either to the        */
  328. /* start of the large object or NIL.                    */
  329. /* In the latter case black list the address current.            */
  330. /* Returns NIL without black listing if current points to a block    */
  331. /* with IGNORE_OFF_PAGE set.                        */
  332. /*ARGSUSED*/
  333. word GC_find_start(current, hhdr)
  334. register word current;
  335. register hdr * hhdr;
  336. {
  337. #   ifdef ALL_INTERIOR_POINTERS
  338.     if (hhdr != 0) {
  339.         register word orig = current;
  340.         
  341.         current = (word)HBLKPTR(current) + HDR_BYTES;
  342.         do {
  343.           current = current - HBLKSIZE*(word)hhdr;
  344.           hhdr = HDR(current);
  345.         } while(IS_FORWARDING_ADDR_OR_NIL(hhdr));
  346.         /* current points to the start of the large object */
  347.         if (hhdr -> hb_flags & IGNORE_OFF_PAGE) return(0);
  348.         if ((word *)orig - (word *)current
  349.              >= (ptrdiff_t)(hhdr->hb_sz)) {
  350.             /* Pointer past the end of the block */
  351.             GC_ADD_TO_BLACK_LIST_NORMAL(orig);
  352.             return(0);
  353.         }
  354.         return(current);
  355.     } else {
  356.         GC_ADD_TO_BLACK_LIST_NORMAL(current);
  357.         return(0);
  358.         }
  359. #   else
  360.         GC_ADD_TO_BLACK_LIST_NORMAL(current);
  361.         return(0);
  362. #   endif
  363. }
  364.  
  365. void GC_invalidate_mark_state()
  366. {
  367.     GC_mark_state = MS_INVALID;
  368.     GC_mark_stack_top = GC_mark_stack-1;
  369. }
  370.  
  371. mse * GC_signal_mark_stack_overflow(msp)
  372. mse * msp;
  373. {
  374.     GC_mark_state = MS_INVALID;
  375. #   ifdef PRINTSTATS
  376.     GC_printf1("Mark stack overflow; current size = %lu entries\n",
  377.                 GC_mark_stack_size);
  378. #    endif
  379.      return(msp-INITIAL_MARK_STACK_SIZE/8);
  380. }
  381.  
  382.  
  383. /*
  384.  * Mark objects pointed to by the regions described by
  385.  * mark stack entries between GC_mark_stack and GC_mark_stack_top,
  386.  * inclusive.  Assumes the upper limit of a mark stack entry
  387.  * is never 0.  A mark stack entry never has size 0.
  388.  * We try to traverse on the order of a hblk of memory before we return.
  389.  * Caller is responsible for calling this until the mark stack is empty.
  390.  */
  391. void GC_mark_from_mark_stack()
  392. {
  393.   mse * GC_mark_stack_reg = GC_mark_stack;
  394.   mse * GC_mark_stack_top_reg = GC_mark_stack_top;
  395.   mse * mark_stack_limit = &(GC_mark_stack[GC_mark_stack_size]);
  396.   int credit = HBLKSIZE;    /* Remaining credit for marking work    */
  397.   register word * current_p;    /* Pointer to current candidate ptr.    */
  398.   register word current;    /* Candidate pointer.            */
  399.   register word * limit;    /* (Incl) limit of current candidate     */
  400.                   /* range                */
  401.   register word descr;
  402.   register ptr_t greatest_ha = GC_greatest_plausible_heap_addr;
  403.   register ptr_t least_ha = GC_least_plausible_heap_addr;
  404. # define SPLIT_RANGE_WORDS 128  /* Must be power of 2.        */
  405.  
  406.   GC_objects_are_marked = TRUE;
  407. # ifdef OS2 /* Use untweaked version to circumvent compiler problem */
  408.   while (GC_mark_stack_top_reg >= GC_mark_stack_reg && credit >= 0) {
  409. # else
  410.   while ((((ptr_t)GC_mark_stack_top_reg - (ptr_t)GC_mark_stack_reg) | credit)
  411.       >= 0) {
  412. # endif
  413.     current_p = GC_mark_stack_top_reg -> mse_start;
  414.     descr = GC_mark_stack_top_reg -> mse_descr;
  415.   retry:  
  416.     if (descr & ((~(WORDS_TO_BYTES(SPLIT_RANGE_WORDS) - 1)) | DS_TAGS)) {
  417.       word tag = descr & DS_TAGS;
  418.       
  419.       switch(tag) {
  420.         case DS_LENGTH:
  421.           /* Large length.                            */
  422.           /* Process part of the range to avoid pushing too much on the    */
  423.           /* stack.                            */
  424.           GC_mark_stack_top_reg -> mse_start =
  425.              limit = current_p + SPLIT_RANGE_WORDS-1;
  426.           GC_mark_stack_top_reg -> mse_descr -=
  427.                   WORDS_TO_BYTES(SPLIT_RANGE_WORDS-1);
  428.           /* Make sure that pointers overlapping the two ranges are    */
  429.           /* considered.                         */
  430.           limit = (word *)((char *)limit + sizeof(word) - ALIGNMENT);
  431.           break;
  432.         case DS_BITMAP:
  433.           GC_mark_stack_top_reg--;
  434.           descr &= ~DS_TAGS;
  435.           credit -= WORDS_TO_BYTES(WORDSZ/2); /* guess */
  436.           while (descr != 0) {
  437.             if ((signed_word)descr < 0) {
  438.               current = *current_p++;
  439.               descr <<= 1;
  440.               if ((ptr_t)current < least_ha) continue;
  441.               if ((ptr_t)current >= greatest_ha) continue;
  442.               PUSH_CONTENTS(current, GC_mark_stack_top_reg, mark_stack_limit);
  443.             } else {
  444.               descr <<= 1;
  445.               current_p++;
  446.             }
  447.           }
  448.           continue;
  449.         case DS_PROC:
  450.           GC_mark_stack_top_reg--;
  451.           credit -= PROC_BYTES;
  452.           GC_mark_stack_top_reg =
  453.               (*PROC(descr))
  454.                       (current_p, GC_mark_stack_top_reg,
  455.                       mark_stack_limit, ENV(descr));
  456.           continue;
  457.         case DS_PER_OBJECT:
  458.           descr = *(word *)((ptr_t)current_p + descr - tag);
  459.           goto retry;
  460.       }
  461.     } else {
  462.       GC_mark_stack_top_reg--;
  463.       limit = (word *)(((ptr_t)current_p) + (word)descr);
  464.     }
  465.     /* The simple case in which we're scanning a range.    */
  466.     credit -= (ptr_t)limit - (ptr_t)current_p;
  467.     limit -= 1;
  468.     while (current_p <= limit) {
  469.       current = *current_p;
  470.       current_p = (word *)((char *)current_p + ALIGNMENT);
  471.       if ((ptr_t)current < least_ha) continue;
  472.       if ((ptr_t)current >= greatest_ha) continue;
  473.       PUSH_CONTENTS(current, GC_mark_stack_top_reg, mark_stack_limit);
  474.     }
  475.   }
  476.   GC_mark_stack_top = GC_mark_stack_top_reg;
  477. }
  478.  
  479. /* Allocate or reallocate space for mark stack of size s words  */
  480. /* May silently fail.                        */
  481. static void alloc_mark_stack(n)
  482. word n;
  483. {
  484.     mse * new_stack = (mse *)GC_scratch_alloc(n * sizeof(struct ms_entry));
  485.     
  486.     GC_mark_stack_too_small = FALSE;
  487.     if (GC_mark_stack_size != 0) {
  488.         if (new_stack != 0) {
  489.           word displ = HBLKDISPL(GC_mark_stack);
  490.           word size = GC_mark_stack_size * sizeof(struct ms_entry);
  491.           
  492.           /* Recycle old space */
  493.             if (displ == 0) {
  494.               GC_add_to_heap((struct hblk *)GC_mark_stack, size);
  495.         } else {
  496.           GC_add_to_heap((struct hblk *)
  497.                       ((word)GC_mark_stack - displ + HBLKSIZE),
  498.                        size - HBLKSIZE);
  499.         }
  500.           GC_mark_stack = new_stack;
  501.           GC_mark_stack_size = n;
  502. #      ifdef PRINTSTATS
  503.           GC_printf1("Grew mark stack to %lu frames\n",
  504.                  (unsigned long) GC_mark_stack_size);
  505. #      endif
  506.         } else {
  507. #      ifdef PRINTSTATS
  508.           GC_printf1("Failed to grow mark stack to %lu frames\n",
  509.                  (unsigned long) n);
  510. #      endif
  511.         }
  512.     } else {
  513.         if (new_stack == 0) {
  514.             GC_err_printf0("No space for mark stack\n");
  515.             EXIT();
  516.         }
  517.         GC_mark_stack = new_stack;
  518.         GC_mark_stack_size = n;
  519.     }
  520.     GC_mark_stack_top = GC_mark_stack-1;
  521. }
  522.  
  523. void GC_mark_init()
  524. {
  525.     alloc_mark_stack(INITIAL_MARK_STACK_SIZE);
  526. }
  527.  
  528. /*
  529.  * Push all locations between b and t onto the mark stack.
  530.  * b is the first location to be checked. t is one past the last
  531.  * location to be checked.
  532.  * Should only be used if there is no possibility of mark stack
  533.  * overflow.
  534.  */
  535. void GC_push_all(bottom, top)
  536. ptr_t bottom;
  537. ptr_t top;
  538. {
  539.     register word length;
  540.     
  541.     bottom = (ptr_t)(((word) bottom + ALIGNMENT-1) & ~(ALIGNMENT-1));
  542.     top = (ptr_t)(((word) top) & ~(ALIGNMENT-1));
  543.     if (top == 0 || bottom == top) return;
  544.     GC_mark_stack_top++;
  545.     if (GC_mark_stack_top >= GC_mark_stack + GC_mark_stack_size) {
  546.     ABORT("unexpected mark stack overflow");
  547.     }
  548.     length = top - bottom;
  549. #   if DS_TAGS > ALIGNMENT - 1
  550.     length += DS_TAGS;
  551.     length &= ~DS_TAGS;
  552. #   endif
  553.     GC_mark_stack_top -> mse_start = (word *)bottom;
  554.     GC_mark_stack_top -> mse_descr = length;
  555. }
  556.  
  557. /*
  558.  * Analogous to the above, but push only those pages that may have been
  559.  * dirtied.  A block h is assumed dirty if dirty_fn(h) != 0.
  560.  * We use push_fn to actually push the block.
  561.  * Will not overflow mark stack if push_fn pushes a small fixed number
  562.  * of entries.  (This is invoked only if push_fn pushes a single entry,
  563.  * or if it marks each object before pushing it, thus ensuring progress
  564.  * in the event of a stack overflow.)
  565.  */
  566. void GC_push_dirty(bottom, top, dirty_fn, push_fn)
  567. ptr_t bottom;
  568. ptr_t top;
  569. int (*dirty_fn)(/* struct hblk * h */);
  570. void (*push_fn)(/* ptr_t bottom, ptr_t top */);
  571. {
  572.     register struct hblk * h;
  573.  
  574.     bottom = (ptr_t)(((long) bottom + ALIGNMENT-1) & ~(ALIGNMENT-1));
  575.     top = (ptr_t)(((long) top) & ~(ALIGNMENT-1));
  576.  
  577.     if (top == 0 || bottom == top) return;
  578.     h = HBLKPTR(bottom + HBLKSIZE);
  579.     if (top <= (ptr_t) h) {
  580.       if ((*dirty_fn)(h-1)) {
  581.         (*push_fn)(bottom, top);
  582.     }
  583.     return;
  584.     }
  585.     if ((*dirty_fn)(h-1)) {
  586.         (*push_fn)(bottom, (ptr_t)h);
  587.     }
  588.     while ((ptr_t)(h+1) <= top) {
  589.     if ((*dirty_fn)(h)) {
  590.         if ((word)(GC_mark_stack_top - GC_mark_stack)
  591.         > 3 * GC_mark_stack_size / 4) {
  592.          /* Danger of mark stack overflow */
  593.         (*push_fn)((ptr_t)h, top);
  594.         return;
  595.         } else {
  596.         (*push_fn)((ptr_t)h, (ptr_t)(h+1));
  597.         }
  598.     }
  599.     h++;
  600.     }
  601.     if ((ptr_t)h != top) {
  602.     if ((*dirty_fn)(h)) {
  603.             (*push_fn)((ptr_t)h, top);
  604.         }
  605.     }
  606.     if (GC_mark_stack_top >= GC_mark_stack + GC_mark_stack_size) {
  607.         ABORT("unexpected mark stack overflow");
  608.     }
  609. }
  610.  
  611. # ifndef SMALL_CONFIG
  612. void GC_push_conditional(bottom, top, all)
  613. ptr_t bottom;
  614. ptr_t top;
  615. {
  616.     if (all) {
  617.       if (GC_dirty_maintained) {
  618. #    ifdef PROC_VDB
  619.         /* Pages that were never dirtied cannot contain pointers    */
  620.         GC_push_dirty(bottom, top, GC_page_was_ever_dirty, GC_push_all);
  621. #    else
  622.         GC_push_all(bottom, top);
  623. #    endif
  624.       } else {
  625.           GC_push_all(bottom, top);
  626.       }
  627.     } else {
  628.     GC_push_dirty(bottom, top, GC_page_was_dirty, GC_push_all);
  629.     }
  630. }
  631. #endif
  632.  
  633. # ifdef MSWIN32
  634.   void __cdecl GC_push_one(p)
  635. # else
  636.   void GC_push_one(p)
  637. # endif
  638. word p;
  639. {
  640.     GC_PUSH_ONE_STACK(p);
  641. }
  642.  
  643. # ifdef __STDC__
  644. #   define BASE(p) (word)GC_base((void *)(p))
  645. # else
  646. #   define BASE(p) (word)GC_base((char *)(p))
  647. # endif
  648.  
  649. /* As above, but argument passed preliminary test. */
  650. void GC_push_one_checked(p, interior_ptrs)
  651. register word p;
  652. register bool interior_ptrs;
  653. {
  654.     register word r;
  655.     register hdr * hhdr; 
  656.     register int displ;
  657.   
  658.     GET_HDR(p, hhdr);
  659.     if (IS_FORWARDING_ADDR_OR_NIL(hhdr)) {
  660.         if (hhdr != 0 && interior_ptrs) {
  661.           r = BASE(p);
  662.       hhdr = HDR(r);
  663.       displ = BYTES_TO_WORDS(HBLKDISPL(r));
  664.     } else {
  665.       hhdr = 0;
  666.     }
  667.     } else {
  668.         register map_entry_type map_entry;
  669.         
  670.         displ = HBLKDISPL(p);
  671.         map_entry = MAP_ENTRY((hhdr -> hb_map), displ);
  672.         if (map_entry == OBJ_INVALID) {
  673.           if (interior_ptrs) {
  674.             r = BASE(p);
  675.         displ = BYTES_TO_WORDS(HBLKDISPL(r));
  676.         if (r == 0) hhdr = 0;
  677.           } else {
  678.             hhdr = 0;
  679.           }
  680.         } else {
  681.           displ = BYTES_TO_WORDS(displ);
  682.           displ -= map_entry;
  683.           r = (word)((word *)(HBLKPTR(p)) + displ);
  684.         }
  685.     }
  686.     /* If hhdr != 0 then r == GC_base(p), only we did it faster. */
  687.     /* displ is the word index within the block.         */
  688.     if (hhdr == 0) {
  689.         if (interior_ptrs) {
  690.         GC_add_to_black_list_stack(p);
  691.     } else {
  692.         GC_ADD_TO_BLACK_LIST_NORMAL(p);
  693.     }
  694.     } else {
  695.     if (!mark_bit_from_hdr(hhdr, displ)) {
  696.         set_mark_bit_from_hdr(hhdr, displ);
  697.         PUSH_OBJ((word *)r, hhdr, GC_mark_stack_top,
  698.                  &(GC_mark_stack[GC_mark_stack_size]));
  699.     }
  700.     }
  701. }
  702.  
  703. # ifdef TRACE_BUF
  704.  
  705. # define TRACE_ENTRIES 1000
  706.  
  707. struct trace_entry {
  708.     char * kind;
  709.     word gc_no;
  710.     word words_allocd;
  711.     word arg1;
  712.     word arg2;
  713. } GC_trace_buf[TRACE_ENTRIES];
  714.  
  715. int GC_trace_buf_ptr = 0;
  716.  
  717. void GC_add_trace_entry(char *kind, word arg1, word arg2)
  718. {
  719.     GC_trace_buf[GC_trace_buf_ptr].kind = kind;
  720.     GC_trace_buf[GC_trace_buf_ptr].gc_no = GC_gc_no;
  721.     GC_trace_buf[GC_trace_buf_ptr].words_allocd = GC_words_allocd;
  722.     GC_trace_buf[GC_trace_buf_ptr].arg1 = arg1 ^ 0x80000000;
  723.     GC_trace_buf[GC_trace_buf_ptr].arg2 = arg2 ^ 0x80000000;
  724.     GC_trace_buf_ptr++;
  725.     if (GC_trace_buf_ptr >= TRACE_ENTRIES) GC_trace_buf_ptr = 0;
  726. }
  727.  
  728. void GC_print_trace(word gc_no, bool lock)
  729. {
  730.     int i;
  731.     struct trace_entry *p;
  732.     
  733.     if (lock) LOCK();
  734.     for (i = GC_trace_buf_ptr-1; i != GC_trace_buf_ptr; i--) {
  735.         if (i < 0) i = TRACE_ENTRIES-1;
  736.         p = GC_trace_buf + i;
  737.         if (p -> gc_no < gc_no || p -> kind == 0) return;
  738.         printf("Trace:%s (gc:%d,words:%d) 0x%X, 0x%X\n",
  739.             p -> kind, p -> gc_no, p -> words_allocd,
  740.             (p -> arg1) ^ 0x80000000, (p -> arg2) ^ 0x80000000);
  741.     }
  742.     printf("Trace incomplete\n");
  743.     if (lock) UNLOCK();
  744. }
  745.  
  746. # endif /* TRACE_BUF */
  747.  
  748. /*
  749.  * A version of GC_push_all that treats all interior pointers as valid
  750.  */
  751. void GC_push_all_stack(bottom, top)
  752. ptr_t bottom;
  753. ptr_t top;
  754. {
  755. # ifdef ALL_INTERIOR_POINTERS
  756.     GC_push_all(bottom, top);
  757. #   ifdef TRACE_BUF
  758.         GC_add_trace_entry("GC_push_all_stack", bottom, top);
  759. #   endif
  760. # else
  761.     word * b = (word *)(((long) bottom + ALIGNMENT-1) & ~(ALIGNMENT-1));
  762.     word * t = (word *)(((long) top) & ~(ALIGNMENT-1));
  763.     register word *p;
  764.     register word q;
  765.     register word *lim;
  766.     register ptr_t greatest_ha = GC_greatest_plausible_heap_addr;
  767.     register ptr_t least_ha = GC_least_plausible_heap_addr;
  768. #   define GC_greatest_plausible_heap_addr greatest_ha
  769. #   define GC_least_plausible_heap_addr least_ha
  770.  
  771.     if (top == 0) return;
  772.     /* check all pointers in range and put in push if they appear */
  773.     /* to be valid.                          */
  774.       lim = t - 1 /* longword */;
  775.       for (p = b; p <= lim; p = (word *)(((char *)p) + ALIGNMENT)) {
  776.     q = *p;
  777.     GC_PUSH_ONE_STACK(q);
  778.       }
  779. #   undef GC_greatest_plausible_heap_addr
  780. #   undef GC_least_plausible_heap_addr
  781. # endif
  782. }
  783.  
  784. #ifndef SMALL_CONFIG
  785. /* Push all objects reachable from marked objects in the given block */
  786. /* of size 1 objects.                             */
  787. void GC_push_marked1(h, hhdr)
  788. struct hblk *h;
  789. register hdr * hhdr;
  790. {
  791.     word * mark_word_addr = &(hhdr->hb_marks[divWORDSZ(HDR_WORDS)]);
  792.     register word *p;
  793.     word *plim;
  794.     register int i;
  795.     register word q;
  796.     register word mark_word;
  797.     register ptr_t greatest_ha = GC_greatest_plausible_heap_addr;
  798.     register ptr_t least_ha = GC_least_plausible_heap_addr;
  799. #   define GC_greatest_plausible_heap_addr greatest_ha
  800. #   define GC_least_plausible_heap_addr least_ha
  801.     
  802.     p = (word *)(h->hb_body);
  803.     plim = (word *)(((word)h) + HBLKSIZE);
  804.  
  805.     /* go through all words in block */
  806.     while( p < plim )  {
  807.         mark_word = *mark_word_addr++;
  808.         i = 0;
  809.         while(mark_word != 0) {
  810.           if (mark_word & 1) {
  811.               q = p[i];
  812.               GC_PUSH_ONE_HEAP(q);
  813.           }
  814.           i++;
  815.           mark_word >>= 1;
  816.         }
  817.         p += WORDSZ;
  818.     }
  819. #   undef GC_greatest_plausible_heap_addr
  820. #   undef GC_least_plausible_heap_addr        
  821. }
  822.  
  823.  
  824. #ifndef UNALIGNED
  825.  
  826. /* Push all objects reachable from marked objects in the given block */
  827. /* of size 2 objects.                             */
  828. void GC_push_marked2(h, hhdr)
  829. struct hblk *h;
  830. register hdr * hhdr;
  831. {
  832.     word * mark_word_addr = &(hhdr->hb_marks[divWORDSZ(HDR_WORDS)]);
  833.     register word *p;
  834.     word *plim;
  835.     register int i;
  836.     register word q;
  837.     register word mark_word;
  838.     register ptr_t greatest_ha = GC_greatest_plausible_heap_addr;
  839.     register ptr_t least_ha = GC_least_plausible_heap_addr;
  840. #   define GC_greatest_plausible_heap_addr greatest_ha
  841. #   define GC_least_plausible_heap_addr least_ha
  842.     
  843.     p = (word *)(h->hb_body);
  844.     plim = (word *)(((word)h) + HBLKSIZE);
  845.  
  846.     /* go through all words in block */
  847.     while( p < plim )  {
  848.         mark_word = *mark_word_addr++;
  849.         i = 0;
  850.         while(mark_word != 0) {
  851.           if (mark_word & 1) {
  852.               q = p[i];
  853.               GC_PUSH_ONE_HEAP(q);
  854.               q = p[i+1];
  855.               GC_PUSH_ONE_HEAP(q);
  856.           }
  857.           i += 2;
  858.           mark_word >>= 2;
  859.         }
  860.         p += WORDSZ;
  861.     }
  862. #   undef GC_greatest_plausible_heap_addr
  863. #   undef GC_least_plausible_heap_addr        
  864. }
  865.  
  866. /* Push all objects reachable from marked objects in the given block */
  867. /* of size 4 objects.                             */
  868. /* There is a risk of mark stack overflow here.  But we handle that. */
  869. /* And only unmarked objects get pushed, so it's not very likely.    */
  870. void GC_push_marked4(h, hhdr)
  871. struct hblk *h;
  872. register hdr * hhdr;
  873. {
  874.     word * mark_word_addr = &(hhdr->hb_marks[divWORDSZ(HDR_WORDS)]);
  875.     register word *p;
  876.     word *plim;
  877.     register int i;
  878.     register word q;
  879.     register word mark_word;
  880.     register ptr_t greatest_ha = GC_greatest_plausible_heap_addr;
  881.     register ptr_t least_ha = GC_least_plausible_heap_addr;
  882. #   define GC_greatest_plausible_heap_addr greatest_ha
  883. #   define GC_least_plausible_heap_addr least_ha
  884.     
  885.     p = (word *)(h->hb_body);
  886.     plim = (word *)(((word)h) + HBLKSIZE);
  887.  
  888.     /* go through all words in block */
  889.     while( p < plim )  {
  890.         mark_word = *mark_word_addr++;
  891.         i = 0;
  892.         while(mark_word != 0) {
  893.           if (mark_word & 1) {
  894.               q = p[i];
  895.               GC_PUSH_ONE_HEAP(q);
  896.               q = p[i+1];
  897.               GC_PUSH_ONE_HEAP(q);
  898.               q = p[i+2];
  899.               GC_PUSH_ONE_HEAP(q);
  900.               q = p[i+3];
  901.               GC_PUSH_ONE_HEAP(q);
  902.           }
  903.           i += 4;
  904.           mark_word >>= 4;
  905.         }
  906.         p += WORDSZ;
  907.     }
  908. #   undef GC_greatest_plausible_heap_addr
  909. #   undef GC_least_plausible_heap_addr        
  910. }
  911.  
  912. #endif /* UNALIGNED */
  913.  
  914. #endif /* SMALL_CONFIG */
  915.  
  916. /* Push all objects reachable from marked objects in the given block */
  917. void GC_push_marked(h, hhdr)
  918. struct hblk *h;
  919. register hdr * hhdr;
  920. {
  921.     register int sz = hhdr -> hb_sz;
  922.     register word * p;
  923.     register int word_no;
  924.     register word * lim;
  925.     register mse * GC_mark_stack_top_reg;
  926.     register mse * mark_stack_limit = &(GC_mark_stack[GC_mark_stack_size]);
  927.     
  928.     /* Some quick shortcuts: */
  929.         if (hhdr -> hb_obj_kind == PTRFREE) return;
  930.         if (GC_block_empty(hhdr)/* nothing marked */) return;
  931. #   ifdef GATHERSTATS
  932.         GC_n_rescuing_pages++;
  933. #   endif
  934.     GC_objects_are_marked = TRUE;
  935.     if (sz > MAXOBJSZ) {
  936.         lim = (word *)(h + 1);
  937.     } else {
  938.         lim = (word *)(h + 1) - sz;
  939.     }
  940.     
  941.     switch(sz) {
  942. #   if !defined(SMALL_CONFIG)    
  943.      case 1:
  944.        GC_push_marked1(h, hhdr);
  945.        break;
  946. #   endif
  947. #   if !defined(SMALL_CONFIG) && !defined(UNALIGNED)
  948.      case 2:
  949.        GC_push_marked2(h, hhdr);
  950.        break;
  951.      case 4:
  952.        GC_push_marked4(h, hhdr);
  953.        break;
  954. #   endif       
  955.      default:
  956.       GC_mark_stack_top_reg = GC_mark_stack_top;
  957.       for (p = (word *)h + HDR_WORDS, word_no = HDR_WORDS; p <= lim;
  958.          p += sz, word_no += sz) {
  959.          /* This ignores user specified mark procs.  This currently    */
  960.          /* doesn't matter, since marking from the whole object        */
  961.          /* is always sufficient, and we will eventually use the user    */
  962.          /* mark proc to avoid any bogus pointers.            */
  963.          if (mark_bit_from_hdr(hhdr, word_no)) {
  964.            /* Mark from fields inside the object */
  965.              PUSH_OBJ((word *)p, hhdr, GC_mark_stack_top_reg, mark_stack_limit);
  966. #         ifdef GATHERSTATS
  967.         /* Subtract this object from total, since it was    */
  968.         /* added in twice.                    */
  969.         GC_composite_in_use -= sz;
  970. #         endif
  971.          }
  972.       }
  973.       GC_mark_stack_top = GC_mark_stack_top_reg;
  974.     }
  975. }
  976.  
  977. #ifndef SMALL_CONFIG
  978. /* Test whether any page in the given block is dirty    */
  979. bool GC_block_was_dirty(h, hhdr)
  980. struct hblk *h;
  981. register hdr * hhdr;
  982. {
  983.     register int sz = hhdr -> hb_sz;
  984.     
  985.     if (sz < MAXOBJSZ) {
  986.          return(GC_page_was_dirty(h));
  987.     } else {
  988.          register ptr_t p = (ptr_t)h;
  989.          sz += HDR_WORDS;
  990.          sz = WORDS_TO_BYTES(sz);
  991.          while (p < (ptr_t)h + sz) {
  992.              if (GC_page_was_dirty((struct hblk *)p)) return(TRUE);
  993.              p += HBLKSIZE;
  994.          }
  995.          return(FALSE);
  996.     }
  997. }
  998. #endif /* SMALL_CONFIG */
  999.  
  1000. /* Similar to GC_push_next_marked, but return address of next block    */
  1001. struct hblk * GC_push_next_marked(h)
  1002. struct hblk *h;
  1003. {
  1004.     register hdr * hhdr;
  1005.     
  1006.     h = GC_next_block(h);
  1007.     if (h == 0) return(0);
  1008.     hhdr = HDR(h);
  1009.     GC_push_marked(h, hhdr);
  1010.     return(h + OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz));
  1011. }
  1012.  
  1013. #ifndef SMALL_CONFIG
  1014. /* Identical to above, but mark only from dirty pages    */
  1015. struct hblk * GC_push_next_marked_dirty(h)
  1016. struct hblk *h;
  1017. {
  1018.     register hdr * hhdr = HDR(h);
  1019.     
  1020.     if (!GC_dirty_maintained) { ABORT("dirty bits not set up"); }
  1021.     for (;;) {
  1022.         h = GC_next_block(h);
  1023.         if (h == 0) return(0);
  1024.         hhdr = HDR(h);
  1025. #    ifdef STUBBORN_ALLOC
  1026.           if (hhdr -> hb_obj_kind == STUBBORN) {
  1027.             if (GC_page_was_changed(h) && GC_block_was_dirty(h, hhdr)) {
  1028.                 break;
  1029.             }
  1030.           } else {
  1031.             if (GC_block_was_dirty(h, hhdr)) break;
  1032.           }
  1033. #    else
  1034.       if (GC_block_was_dirty(h, hhdr)) break;
  1035. #    endif
  1036.         h += OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz);
  1037.     }
  1038.     GC_push_marked(h, hhdr);
  1039.     return(h + OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz));
  1040. }
  1041. #endif
  1042.  
  1043. /* Similar to above, but for uncollectable pages.  Needed since we    */
  1044. /* do not clear marks for such pages, even for full collections.    */
  1045. struct hblk * GC_push_next_marked_uncollectable(h)
  1046. struct hblk *h;
  1047. {
  1048.     register hdr * hhdr = HDR(h);
  1049.     
  1050.     for (;;) {
  1051.         h = GC_next_block(h);
  1052.         if (h == 0) return(0);
  1053.         hhdr = HDR(h);
  1054.     if (hhdr -> hb_obj_kind == UNCOLLECTABLE) break;
  1055.         h += OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz);
  1056.     }
  1057.     GC_push_marked(h, hhdr);
  1058.     return(h + OBJ_SZ_TO_BLOCKS(hhdr -> hb_sz));
  1059. }
  1060.  
  1061.  
  1062.